package 接雨水;

/**
 * createTime: 2025/5/25 23:01
 * description:
 *
 * @author AirMan
 */
public class Solution2 {
    public int trap(int[] height) {
        // 双指针法（等同于动态规划）
        // 双指针是按列计算，找到左边和右边的最高板子中的最短板
        // 利用双指针记录每一个元素左边的最大值，右边的最大值，然后根据哪一个板子短觉得存水量
        int result = 0;
        int size = height.length;
        int[] leftMax = new int[size];
        int[] rightMax = new int[size];
        // 第一个格子和最后一个格子不能存放水，直接跳过
        leftMax[0] = height[0]; // 初始化第一个格子的最值，方便正数第二个格子的计算
        for (int i = 1; i < size - 1; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        rightMax[size - 1] = height[size - 1];  // 初始化最后一个格子的最值，方便倒数第二个格子的计算
        for (int i = size - 2; i >= 1; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        // 计算每一个格子的蓄水量：左右两边高板子的最低板子和凹槽(当前元素)的高差 × 宽度(1)
        for (int i = 1; i < size - 1; i++) {
            int heightDiff = Math.min(leftMax[i], rightMax[i]) - height[i];
            if (heightDiff > 0) {
                result += heightDiff * 1;
            }
        }

        return result;
    }
}
